package com.zjsru.studyplan1;

/**
 * 最大岛屿的面积
 * <p>
 * 输入：grid = [[0,0,1,0,0,0,0,1,0,0,0,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],
 * [0,1,1,0,1,0,0,0,0,0,0,0,0],[0,1,0,0,1,1,0,0,1,0,1,0,0],
 * [0,1,0,0,1,1,0,0,1,1,1,0,0],[0,0,0,0,0,0,0,0,0,0,1,0,0],
 * [0,0,0,0,0,0,0,1,1,1,0,0,0],[0,0,0,0,0,0,0,1,1,0,0,0,0]]
 * 输出：6
 * 解释：答案不应该是 11 ，因为岛屿只能包含水平或垂直这四个方向上的 1 。
 */
public class maxAreaOfIsland {
    public int maxAreaOfIsland(int[][] grid) {
        int row = grid.length;
        int col = grid[0].length;
        int ans = 0;
        for(int i =0; i!=row;i++){
            for(int j =0; j!=col;j++){
                ans = Math.max(ans,dfs(grid,i,j));
            }
        }
        return ans;
    }
    private int dfs(int[][] grid, int cur_i, int cur_j) {
        if(cur_i < 0 || cur_j < 0|| grid.length ==cur_i ||grid[0].length == cur_j|| grid[cur_i][cur_j]!=1){
            return 0;
        }
        grid[cur_i][cur_j] =0;
        int[] dx = {0,0,1,-1};
        int[] dy = {1,-1,0,0};
        int ans = 1;
        for(int index = 0;index !=4 ;index++){
            int next_i = cur_i + dx[index],next_j = cur_j + dy[index];
            ans += dfs(grid,next_i,next_j);

        }
        return ans;
    }

    public static void main(String[] args) {
        maxAreaOfIsland maxAreaOfIsland = new maxAreaOfIsland();
        int[][] gird = new int[][]{{0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0}, {0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0}, {0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0},
                {0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 0, 0}, {0, 1, 0, 0, 1, 1, 0, 0, 1, 1, 1, 0, 0}, {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0}, {0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0}
                , {0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0}};
        System.out.println(maxAreaOfIsland.maxAreaOfIsland(gird));
    }
}
